package me.leetcodepractice;

public class E05Leetcode82 {
    // 链表去重，重复元素全部去掉
    // 方法一：递归
    /*public ListNode deleteDuplicates1(ListNode p) {
        if (p == null || p.next == null) {
            return p;
        }
        if (p.val == p.next.val) {
            // 一直往后找重复的元素
            ListNode x = p.next.next;
            while (x != null && x.val == p.val) {
                x = x.next;
            }
            // 退出while循环，x就是与p取值不同的节点
            return deleteDuplicates1(x);
        } else {
            p.next = deleteDuplicates1(p.next);
            return p;
        }
    }*/

    // 方法二：非递归实现
    public ListNode deleteDuplicates2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 哨兵节点
        ListNode s = new ListNode(-1, head);
        ListNode p1 = s;
        ListNode p2, p3; // 先不赋值
        // 往后循环的条件
        while ((p2 = p1.next) != null
                && (p3 = p2.next) != null) {
            if (p2.val == p3.val) {
                // 再往后找相同的元素
                while ((p3 = p3.next) != null
                        && (p3.val == p2.val)) {

                }
                // while循环退出，表示找到了值不相同的节点
                // 直接跳过重复的节点
                p1.next = p3;
            } else {
                p1 = p1.next;
            }
        }
        return s.next;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 2, 2, 3, 6);
        System.out.println(head);
        System.out.println(new E05Leetcode82().deleteDuplicates2(head));
    }
}
